BIT Algo/3. Zajęcia/Zadanie 1. (Sprawdzanie, czy zbiory są rozłączne).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Dane są dwa zbiory liczb, reprezentowane przez tablice rozmiarów $ m $ i $ n $, gdzie $ m $ jest znacznie mniejsze od $ n $. Zaproponuj algorytm, który sprawdzi, czy zbiory są rozłączne."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### UWAGA:\n",
    "Ze względu na brak informacji o rozkładzie oraz zakresie liczb, nie możemy wykorzystać Bucket Sorta ani Counting Sorta. Ponieważ liczby mogą być rzeczywiste, ale niekoniecznie całkowite (brak informacji o tym, czy są one całkowite), odpada również Radix Sort. Można by się ewentualnie pokusić o Bucket Sorta z Bucket Sortem do sortowania wiaderek, ale ma on bardzo dużą złożoność pamięciową, w przypadku niekorzystnych danych. Mimo to, zazwyczaj jest on 2-3 razy szybszy od Quick Sorta. Niestety trudno uzasadnić, dlaczego akuret się wybrało taki algorytm, więc lepiej wziąć Quick Sorta, jeżeli w zadaniu nie ma powiedzianego nic, że algorytm ma działać w czasie liniowym, być stabilny lub działać w miejscu, itp."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# I Sposób (najlepszy):"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Aby sprawdzić, czy zbiory są rozłączne, wystarczy sprawdzić, czy mają one część wspólną, a więc, czy choćby jeden element z jednego ze zbiorów (nieważne którego) znajduje się w drugim ze zbiorów. Najłatwiej tego dokonać, poprzez posortowanie mniejszego ze zbiorów (ponieważ sortowanie zawsze zabiera najwięcej czasu, zazwyczaj lepiej sortować mniejsze zbiory danych), a następnie przechodzić liniowo przez NIEPOSORTOWANĄ tablicę (tę większą, odpowiadającą większemu zbiorowi) i sprawdzać wyszukiwaniem binarnym w POSORTOWANEJ (mniejszej) tablicy, czy znajduje się w niej odpowiedni element."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Wyjaśnienie, dlaczego sortujemy mniejszą tablicę"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zastanówmy się, którą z tablic jest lepiej posortować. Wydawałoby się, że większą, bo wtedy wyszukiwanie binarne działa znacznie szybciej (chodzi o to, że skorzystalibyśmy z wyszukiwania binarnego $ m $ razy na tablicy $ n $-elementowej, a to daje nam złożoność $ O(m \\cdot log(n)) < O(n \\cdot log(m)) $ (dla $ m \\ll n $)). Jest to jednak złe podejście, ponieważ dokładna analiza złożoności pokazuje, że sam proces sortowania tej ($ n $-elementowej) tablicy będzie trwał znacznie dłużej niż sortowanie mniejszej ($ m $-elementowej) tablicy."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Niech: <br>\n",
    "$ n $ - długość dłuższej tablicy, <br>\n",
    "$ m $ - długość krótszej tablicy (tu wiemy, że $ m \\ll n $), <br>\n",
    "Wówczas: <br>\n",
    "1. Złożoność przy sortowaniu większej tablicy: <br>\n",
    "$ O(n \\cdot log(n)) + O(m \\cdot log(n)) = O(n \\cdot log(n) + m \\cdot log(n)) \\approx O(n \\cdot log(n)) $ <br>\n",
    "Przykład dla konkretnych wartości: <br>\n",
    "$ n = 2^{32} $, $ m = 2^2 $ <br>\n",
    "Uwaga nieformalny zapis (zakładamy, że jest to logarytm o podstawie $ 2 $, ponieważ mamy do czynienia z wyszukiwaniem binarnym oraz sortowaniem algorytmem QuickSort, w których idea polega na podziale danych na pół): <br>\n",
    "$ O(n \\cdot log(n) + m \\cdot log(n)) = O(2^{32} \\cdot log_2{2^{32}} + 2^2 \\cdot log_2{2^{32})} = O(2^{32} \\cdot 32 + 2^2 \\cdot 32) \\approx O(2^{37}) $ <br>\n",
    "2. Złożoność przy sortowaniu mniejszej tablicy: <br>\n",
    "$ O(m \\cdot log(m)) + O(n \\cdot log(m)) = O(m \\cdot log(m) + n \\cdot log(m)) \\approx O(n \\cdot log(m)) $ <br>\n",
    "Przykład dla konkretnych wartości: <br>\n",
    "$ n = 2^{32} $, $ m = 2^2 $ <br>\n",
    "Uwaga nieformalny zapis (zakładamy, że jet to logarytm o podstawie 2): <br>\n",
    "$ O(m \\cdot log(m) + n \\cdot log(m)) = O(2^2 \\cdot log_2{2^2} + 2^{32} \\cdot log_2{2^2}) = O(2^2 \\cdot 2 + 2^{32} \\cdot 2) \\approx O(2^{33}) $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Na podstawie powyższego przykładu widzimy, że przesortowanie mniejszej tablicy daje nam lepszy rezultat: $ O(2^{33}) < O(2^{37}) $"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Implementacja algorytmu:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def are_disjoint(arr1: list, arr2: list) -> bool:\n",
    "    # Check which array has more elements\n",
    "    if len(arr1) < len(arr2):\n",
    "        shorter = arr1\n",
    "        longer = arr2\n",
    "    else:\n",
    "        shorter = arr2\n",
    "        longer = arr1\n",
    "    # Sort a shorter array\n",
    "    quick_sort(shorter)\n",
    "    # Check using a Binary Search if a shorter array\n",
    "    # has at least element from the longer array\n",
    "    for val in longer:\n",
    "        val_idx = binary_search_first(shorter, val)\n",
    "        if val_idx >= 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "\n",
    "def quick_sort(arr):\n",
    "    _quick_sort(arr, 0, len(arr) - 1)\n",
    "    \n",
    "\n",
    "def _quick_sort(arr, left_idx, right_idx):\n",
    "    while left_idx < right_idx:\n",
    "        pivot_position = _partition(arr, left_idx, right_idx)\n",
    "        \n",
    "        if pivot_position - left_idx < right_idx - pivot_position:\n",
    "            _quick_sort(arr, left_idx, pivot_position)\n",
    "            left_idx = pivot_position + 1  # I removed a tailing recursion\n",
    "        else:\n",
    "            _quick_sort(arr, pivot_position + 1, right_idx)\n",
    "            right_idx = pivot_position  # I removed a tailing recursion\n",
    "        \n",
    "        \n",
    "def _partition(arr, left_idx, right_idx):\n",
    "    pivot = arr[left_idx]\n",
    "    \n",
    "    # Partition an array into 2 subarrays of elements lower than or\n",
    "    # equal to a pivot and of elements greater or equal to a pivot \n",
    "    # (in this partition algorithm pivot isn't placed on a fixed position \n",
    "    # but can be also swapped like all the remaining values)\n",
    "    i = left_idx - 1\n",
    "    j = right_idx + 1\n",
    "    while True:\n",
    "        i += 1\n",
    "        while arr[i] < pivot: i += 1\n",
    "            \n",
    "        j -= 1\n",
    "        while arr[j] > pivot: j -= 1\n",
    "        \n",
    "        if i < j:\n",
    "            _swap(arr, i, j)\n",
    "        else:\n",
    "            return j  # Return a pivot position after the last swap\n",
    "\n",
    "    \n",
    "def _swap(arr, i, j):\n",
    "    arr[i], arr[j] = arr[j], arr[i]\n",
    "\n",
    "\n",
    "def binary_search_first(arr: 'sorted sequence', el: 'searched element') -> int:\n",
    "    left_idx = 0\n",
    "    right_idx = len(arr)-1\n",
    "    \n",
    "    while left_idx <= right_idx:\n",
    "        mid_idx = (left_idx + right_idx) // 2\n",
    "        if el > arr[mid_idx]:\n",
    "            left_idx = mid_idx + 1\n",
    "        else:\n",
    "            right_idx = mid_idx - 1\n",
    "            \n",
    "    return left_idx if left_idx < len(arr) and arr[left_idx] == el else -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "a = [1, 2, 6, 2, 1, 7, 3]\n",
    "b = [0, 5, 5, 4, -4, 12]\n",
    "print(are_disjoint(a, b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "a = [1, 2, 6, 2, 1, 7, 3]\n",
    "b = [0, 5, 5, 4, -4, 12, 2]\n",
    "print(are_disjoint(a, b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "65536 4\n",
      "Expected: True\n",
      "Result:   True\n",
      "Intersecting values: set()\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "longer_length  = 2**16\n",
    "shorter_length = 2**2\n",
    "\n",
    "mul = 100\n",
    "round_ = 3\n",
    "arr1 = [round(random.random() * mul * random.choice([-1, 1]), round_) for _ in range(longer_length)]\n",
    "arr2 = [round(random.random() * mul * random.choice([-1, 1]), round_) for _ in range(shorter_length)]\n",
    "\n",
    "print(len(arr1), len(arr2))\n",
    "intersection = set(arr1) & set(arr2)\n",
    "expected = not bool(intersection)\n",
    "result = are_disjoint(arr1, arr2)\n",
    "print('Expected:', expected)\n",
    "print('Result:  ', result)\n",
    "print('Intersecting values:', intersection)\n",
    "for val in intersection:\n",
    "    print(f'Is {val} in arr1?: {val in arr1}\\tIs {val} in arr2?: {val in arr2}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# II Sposób:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Omówienie algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sortujemy obie tablice, a następnie przeglądamy je liniowo. Jest to wolniejszy algorytm, ale nie wykorzystuje wyszukiwania binarnego."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def are_disjoint(arr1: list, arr2: list) -> bool:\n",
    "    # Sort both arrays\n",
    "    quick_sort(arr1)\n",
    "    quick_sort(arr2)\n",
    "    \n",
    "    if len(arr1) < len(arr2):\n",
    "        shorter = arr1\n",
    "        longer = arr2\n",
    "    else:\n",
    "        shorter = arr2\n",
    "        longer = arr1\n",
    "    # Move linearly through both arrays and check if any of the values\n",
    "    # from the shorter array is in the longer array\n",
    "    long_idx = 0\n",
    "    for val in shorter:\n",
    "        # Move a pointer to the same value candidate\n",
    "        while long_idx < len(longer) and longer[long_idx] < val:\n",
    "            long_idx += 1\n",
    "        if long_idx < len(longer) and longer[long_idx] == val:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "\n",
    "def quick_sort(arr):\n",
    "    _quick_sort(arr, 0, len(arr) - 1)\n",
    "    \n",
    "\n",
    "def _quick_sort(arr, left_idx, right_idx):\n",
    "    while left_idx < right_idx:\n",
    "        pivot_position = _partition(arr, left_idx, right_idx)\n",
    "        \n",
    "        if pivot_position - left_idx < right_idx - pivot_position:\n",
    "            _quick_sort(arr, left_idx, pivot_position)\n",
    "            left_idx = pivot_position + 1  # I removed a tailing recursion\n",
    "        else:\n",
    "            _quick_sort(arr, pivot_position + 1, right_idx)\n",
    "            right_idx = pivot_position  # I removed a tailing recursion\n",
    "        \n",
    "        \n",
    "def _partition(arr, left_idx, right_idx):\n",
    "    pivot = arr[left_idx]\n",
    "    \n",
    "    # Partition an array into 2 subarrays of elements lower than or\n",
    "    # equal to a pivot and of elements greater or equal to a pivot \n",
    "    # (in this partition algorithm pivot isn't placed on a fixed position \n",
    "    # but can be also swapped like all the remaining values)\n",
    "    i = left_idx - 1\n",
    "    j = right_idx + 1\n",
    "    while True:\n",
    "        i += 1\n",
    "        while arr[i] < pivot: i += 1\n",
    "            \n",
    "        j -= 1\n",
    "        while arr[j] > pivot: j -= 1\n",
    "        \n",
    "        if i < j:\n",
    "            _swap(arr, i, j)\n",
    "        else:\n",
    "            return j  # Return a pivot position after the last swap\n",
    "\n",
    "    \n",
    "def _swap(arr, i, j):\n",
    "    arr[i], arr[j] = arr[j], arr[i]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "a = [1, 2, 6, 2, 1, 7, 3]\n",
    "b = [0, 5, 5, 4, -4, 12]\n",
    "print(are_disjoint(a, b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "a = [1, 2, 6, 2, 1, 7, 3]\n",
    "b = [0, 5, 5, 4, -4, 12, 2]\n",
    "print(are_disjoint(a, b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "65536 4\n",
      "Expected: False\n",
      "Result:   False\n",
      "Intersecting values: {23.181}\n",
      "Is 23.181 in arr1?: True\tIs 23.181 in arr2?: True\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "longer_length  = 2**16\n",
    "shorter_length = 2**2\n",
    "\n",
    "mul = 100\n",
    "round_ = 3\n",
    "arr1 = [round(random.random() * mul * random.choice([-1, 1]), round_) for _ in range(longer_length)]\n",
    "arr2 = [round(random.random() * mul * random.choice([-1, 1]), round_) for _ in range(shorter_length)]\n",
    "\n",
    "print(len(arr1), len(arr2))\n",
    "intersection = set(arr1) & set(arr2)\n",
    "expected = not bool(intersection)\n",
    "result = are_disjoint(arr1, arr2)\n",
    "print('Expected:', expected)\n",
    "print('Result:  ', result)\n",
    "print('Intersecting values:', intersection)\n",
    "for val in intersection:\n",
    "    print(f'Is {val} in arr1?: {val in arr1}\\tIs {val} in arr2?: {val in arr2}')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# III Sposób\n",
    "### (Nie mam pewności, czy zostałby zaakceptowany)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Opis algorytmu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Postępujemy podobnie jak w 1. sposobie, ale do sortowania używamy ulepszonej wersji Bucket Sorta (niskie ryzyko najgorszego przyadku, duże ryzyko zajęcia nadmiernej pamięci)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def are_disjoint(arr1: list, arr2: list) -> bool:\n",
    "    # Check which array has more elements\n",
    "    if len(arr1) < len(arr2):\n",
    "        shorter = arr1\n",
    "        longer = arr2\n",
    "    else:\n",
    "        shorter = arr2\n",
    "        longer = arr1\n",
    "    # Sort a shorter array\n",
    "    bucket_sort(shorter)\n",
    "    # Check using a Binary Search if a shorter array\n",
    "    # has at least element from the longer array\n",
    "    for val in longer:\n",
    "        val_idx = binary_search_first(shorter, val)\n",
    "        if val_idx >= 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "\n",
    "# Use k as a thershold which idicates when to start using Insertion Sort\n",
    "def bucket_sort(arr, *, k: 'threshold' = 24):\n",
    "    # If a bucket is small enough, use an Insertion Sort algorithm to\n",
    "    # sort this bucket\n",
    "    if len(arr) <= k:\n",
    "        insertion_sort(arr)\n",
    "    else:\n",
    "        _bucket_sort(arr, k)\n",
    "        \n",
    "        \n",
    "def _bucket_sort(arr, k):\n",
    "    # Store the maximum and the minimum value of a bucket\n",
    "    min_val, max_val = minmax(arr)\n",
    "    # Sort a bucket if only there is more than one unique value\n",
    "    if min_val != max_val:\n",
    "        # Make a threshold a bit smaller as a number of elements in each\n",
    "        # bucket can slightly vary and we don't want to make unnecessary\n",
    "        # recursive calls.\n",
    "        m = int(2/3 * k)\n",
    "        # Create buckets\n",
    "        buckets_count = len(arr) // m + 1\n",
    "        buckets = [[] for _ in range(buckets_count)]\n",
    "        val_interval = (max_val - min_val) / buckets_count\n",
    "        # Distribute values to the proper buckets\n",
    "        for val in arr:\n",
    "            # Calculate the bucket's index depending on how much the \n",
    "            # current value is greater than the lowest one\n",
    "            bucket_idx = int((val - min_val) / val_interval - .5)\n",
    "            buckets[bucket_idx].append(val)\n",
    "        # Sort each bucket separately\n",
    "        for bucket in buckets:\n",
    "            # Bucket sort all of the buckets again\n",
    "            bucket_sort(bucket, k=k)\n",
    "        # Rewrite sorted values from buckets to the inintial array\n",
    "        i = 0\n",
    "        for bucket in buckets:\n",
    "            for val in bucket:\n",
    "                arr[i] = val\n",
    "                i += 1\n",
    "        \n",
    "        \n",
    "def minmax(arr):\n",
    "    global_min = global_max = arr[-1]\n",
    "    \n",
    "    for i in range(0, len(arr)-1, 2):\n",
    "        if arr[i] > arr[i+1]:\n",
    "            if arr[i] > global_max:   global_max = arr[i]\n",
    "            if arr[i+1] < global_min: global_min = arr[i+1]\n",
    "        else:\n",
    "            if arr[i+1] > global_max: global_max = arr[i+1]\n",
    "            if arr[i] < global_min:   global_min = arr[i]\n",
    "    return global_min, global_max\n",
    "\n",
    "\n",
    "def insertion_sort(arr):\n",
    "    for i in range(1, len(arr)):\n",
    "        j = i-1\n",
    "        temp = arr[i]\n",
    "        \n",
    "        while j >= 0 and temp < arr[j]:\n",
    "            arr[j+1] = arr[j]\n",
    "            j -= 1\n",
    "        \n",
    "        arr[j+1] = temp        \n",
    "\n",
    "\n",
    "def binary_search_first(arr: 'sorted sequence', el: 'searched element') -> int:\n",
    "    left_idx = 0\n",
    "    right_idx = len(arr)-1\n",
    "    \n",
    "    while left_idx <= right_idx:\n",
    "        mid_idx = (left_idx + right_idx) // 2\n",
    "        if el > arr[mid_idx]:\n",
    "            left_idx = mid_idx + 1\n",
    "        else:\n",
    "            right_idx = mid_idx - 1\n",
    "            \n",
    "    return left_idx if left_idx < len(arr) and arr[left_idx] == el else -1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "a = [1, 2, 6, 2, 1, 7, 3]\n",
    "b = [0, 5, 5, 4, -4, 12]\n",
    "print(are_disjoint(a, b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n"
     ]
    }
   ],
   "source": [
    "a = [1, 2, 6, 2, 1, 7, 3]\n",
    "b = [0, 5, 5, 4, -4, 12, 2]\n",
    "print(are_disjoint(a, b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Puszczając poniższy test, możemy zauważyć, jak szybko działa sortowanie. Więcej czasu zajmuje wygenerowanie losowych liczb niż działanie tego algorytmu."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1048576 4\n",
      "Expected: True\n",
      "Result:   True\n",
      "Intersecting values: set()\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "longer_length  = 2**20\n",
    "shorter_length = 2**2\n",
    "\n",
    "mul = 1000\n",
    "round_ = 4\n",
    "arr1 = [round(random.random() * mul * random.choice([-1, 1]), round_) for _ in range(longer_length)]\n",
    "arr2 = [round(random.random() * mul * random.choice([-1, 1]), round_) for _ in range(shorter_length)]\n",
    "\n",
    "print(len(arr1), len(arr2))\n",
    "intersection = set(arr1) & set(arr2)\n",
    "expected = not bool(intersection)\n",
    "result = are_disjoint(arr1, arr2)\n",
    "print('Expected:', expected)\n",
    "print('Result:  ', result)\n",
    "print('Intersecting values:', intersection)\n",
    "for val in intersection:\n",
    "    print(f'Is {val} in arr1?: {val in arr1}\\tIs {val} in arr2?: {val in arr2}')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}